package com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.桶排序;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 桶排序 排序 0 - 99 之间的元素
 *
 *  非通用版本
 *
 * @author Baixiaowen
 */
public class BucketSortV1 {

    public List<Integer> sort(List<Integer> A) {
        int k = 100;
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        // 初始化
        for (int i = 0; i < k; i++) {
            buckets.add(new LinkedList<>());
        }

        for (Integer item : A) {
            buckets.get(item % k).add(item);
        }

        for (LinkedList<Integer> bucket : buckets) {
            list.addAll(bucket);
        }
        
        return list;
    }

}
